//
//  Stack.cpp
//  cpp
//
//  Created by xueshan1 on 2019/9/11.
//  Copyright © 2019 xueshan1. All rights reserved.
//

#include <stdio.h>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <stack>

using namespace std;
using std :: vector;

//栈
//先进后出

#pragma mark - 最长有效括号
//给出一个只包含'(' 和')'的字符串，找出其中最长的左右括号正确匹配的合法子串。
//https://blog.csdn.net/hunt_ing/article/details/82822912
//思路: 当前字符c如果是 ( ,则直接压栈; 如果c是 ), 需要分情况考虑.


#pragma mark - 移掉k位数字
//给定一个以字符串表示的非负整数  num，移除这个数中的  k 位数字，使得剩下的数字最小。
//https://blog.csdn.net/huang_wx/article/details/85384531
void removeKDigits(string num,int k){
    stack<int>res;
    
    for (int i = 0; i<num.length(); i++) {
        int number = num[i] - '0';
        
        while (res.size() != 0 && k >0 && number < res.top()) {//当前数字比栈顶小, 栈顶->出栈;
            res.pop();
            k--;
        }
        
        if (number != 0) {
            res.push(number);
        }
        
    }
    
    //删除多余的
    while (res.size() != 0 && k>0) {
        res.pop();
        k--;
    }
    
    
}

